package com.c2b.algorithm.leetcode.base.monotone_stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/steps-to-make-array-non-decreasing/">使数组按非递减顺序排列(Steps to Make Array Non-decreasing)</a>
 * <p>给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。</p>
 * <p>重复执行步骤，直到 nums 变为 非递减 数组，返回所需执行的操作数。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
 *      输出：3
 *      解释：执行下述几个步骤：
 *          - 步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
 *          - 步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
 *          - 步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
 *          [5,7,11,11] 是一个非递减数组，因此，返回 3 。
 *
 * 示例 2：
 *      输入：nums = [4,5,7,7,13]
 *      输出：0
 *      解释：nums 已经是一个非递减数组，因此，返回 0 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>1 <= nums.length <= 10^5</li>
 * <li>-0 <= nums[i] <= 10^9</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/6 17:22
 */
public class LC02289StepsToMakeArrayNonDecreasing_H {

    static class Solution {
        public int totalSteps(int[] nums) {
            int ans = 0;
            Deque<int[]> stack = new ArrayDeque<>();
            for (int currNum : nums) {
                int temp = 0;
                while (!stack.isEmpty() && currNum > stack.peekLast()[0]) {
                    temp = Math.max(temp, stack.pollLast()[1]);
                }
                temp = stack.isEmpty() ? 0 : temp + 1;
                ans = Math.max(ans, temp);
                stack.offerLast(new int[]{currNum, temp});
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.totalSteps(new int[]{5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11}));
        System.out.println(solution.totalSteps(new int[]{4, 5, 7, 7, 13}));
        System.out.println(solution.totalSteps(new int[]{7, 14, 4, 14, 13, 2, 6, 13}));
    }
}
